#pragma once

template<typename T>
class queue {
private:
	struct node {
		node() {}
		node* next;
		T data;
	};

	node *head_internal, *tail_internal;
	unsigned long len_internal;
private:
	node* append_new_node_to_tail() {
		len_internal++;
		if (tail_internal != nullptr) {
			tail_internal->next = new node;
			tail_internal = tail_internal->next;
			return tail_internal;
		}
		else
		{
			head_internal = new node;
			tail_internal = head_internal;
			return head_internal;
		}
	}

	void delete_front_node() {
		if (head_internal != nullptr) {
			auto node_to_delete = head_internal;
			head_internal = head_internal->next;
			delete node_to_delete;
			len_internal--;
		}
	}
public:
	queue() {
		len_internal = 0;
		head_internal = nullptr;
		tail_internal = nullptr;
	}

	~queue() {
		while (len_internal > 0)
			delete_front_node();
	}

	unsigned long len() {
		return len_internal;
	}

	void push(T data) {
		append_new_node_to_tail()->data = data;
	}

	T pop() {
		if (head_internal != nullptr) {
			auto data = head_internal->data;
			delete_front_node();
			return data;
		}
	}
};
